package priv.pront.code.national.acwing.graph;

/**
 * @Description:
 * @Author: pront
 * @Time:2023-05-27 22:14
 */
public class Acwing1128_信使 {

    /*
    SPFA版本
     static int n, m, idx, INF = (int)1e9;
    static Queue<Integer> queue = new LinkedList<>();
    static int[] h, e, ne, w, dist;
    static boolean[] st;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); m = scanner.nextInt();
        h = new int[n + 10];
        e = new int[2 * m + 10];
        ne = new int[2 * m + 10];
        dist = new int[n + 10];
        w = new int[2 * m + 10];
        st = new boolean[n + 10];
        Arrays.fill(h, -1);
        for(int i = 1; i <= m; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            add(a, b, c); add(b, a, c);
        }
        System.out.println(spfa());
    }

    private static int spfa(){
        Arrays.fill(dist, INF);
        dist[1] = 0;
        queue.add(1);
        while(!queue.isEmpty()){
            int cur = queue.poll();
            st[cur] = false;
            for(int i = h[cur]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] > dist[cur] + w[i]){
                    dist[j] = dist[cur] + w[i];
                    if(!st[j]){
                        queue.add(j);
                        st[j] = true;
                    }
                }
            }
        }
        int res = -INF;
        for(int i = 1; i <= n; i++){
            if(res == INF) return -1;
            res = Math.max(res, dist[i]);
        }
        return res;
    }

    private static void add(int a, int b, int c){
        e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
    }
     */

    /*
    Dijkstra 堆优化版本
      static int n, m, idx, INF = (int)1e9;
    static int[] h, e, ne, w, dist;
    static boolean[] st;
    static PriorityQueue<int[]> heap = new PriorityQueue<>(new Com());
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); m = scanner.nextInt();
        h = new int[n + 10];
        e = new int[2 * m + 10];
        w =  new int[2 * m + 10];
        ne = new int[2 * m + 10];
        dist = new int[n + 10];
        st = new boolean[n + 10];
        Arrays.fill(h, -1);
        for(int i = 1; i <= m; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            add(a, b, c); add(b, a, c);
        }

        System.out.println(dijkstra());
    }

    private static int dijkstra(){
        Arrays.fill(dist, INF);
        dist[1] = 0;
        heap.add(new int[]{0, 1});
        while(!heap.isEmpty()){
            int[] cur = heap.poll();
            int ver = cur[1], distance = cur[0];
            if(st[ver]) continue;
            st[ver] = true;
            for(int i = h[ver]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] > distance + w[i]){
                    dist[j] = distance + w[i];
                    heap.offer(new int[]{dist[j] ,j});
                }
            }
        }
        int res = -INF;
        for(int i = 1; i <= n; i++){
            if(dist[i] == INF) return -1;
            res = Math.max(res, dist[i]);
        }
        return res;
    }

    private static void add(int a, int b, int c){
        e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++;
    }


      private static class Com implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];
        }
    }
     */
}
